from typing import *


class Solution:

    def combinationSum(self, candidates: List[int],
                       target: int) -> List[List[int]]:

        ans = []

        def f(idx, arr: list, tot):
            if tot > target:
                return
            if idx == len(candidates):
                if tot == target:
                    ans.append(arr.copy())
                return
            f(idx + 1, arr, tot)
            arr.append(candidates[idx])
            f(idx, arr ,tot + candidates[idx])
            arr.pop()

        f(0, [], 0)
        return ans